#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<ctype.h>

//
//void print(int** a) {
//
//	for (int i = 0; i < 2; ++i) {
//		for (int j = 0; j < 3; ++j) {
//			printf("%d ", a[i][j]);
//		}
//	}
//}
//
//int main() {
//	int** arr = (int**)malloc(sizeof(int*) * 2);
//
//	for (int i = 0; i < 2; ++i) {
//		arr[i] = (int*)malloc(sizeof(int) * 3);
//	}
//
//	int k = 0;
//	for (int i = 0; i < 2; ++i) {
//		for (int j = 0; j < 3; ++j) {
//			arr[i][j] = k;
//			k++;
//		}
//	}
//	print(arr);
//	return 0;
//}

//strlen 
//int my_strlen(const char* str) {
//	if (*str == '\0') {
//		return 0;
//	}
//
//	return my_strlen(str + 1) + 1;
//}

int my_strlen(const char* str) {
	assert(str);

	int count = 0;
	while (*str) {
		count++;
		str++;
	}

	return count;
}

//strcpy
//char* my_strcpy(char* dst, const char* src) {
//	assert(dst && src);
//
//	char* ret = dst;
//	while (*src) {
//		*dst = *src;
//		dst++;
//		src++;
//	}
//	*dst = *src;
//	return dst;
//}

//strcat
//char* my_strcat(char* dst, const char* src) {
//	assert(dst && src);
//
//	char* ret = dst;
//
//	//找到\0位置
//	while (*dst) {
//		dst++;
//	}
//
//	while (*src) {
//		*dst = *src;
//		dst++;
//		src++;
//	}
//
//	*dst = '\0';
//
//	return ret;
//}

//memcpy
void* my_memcpy(void* dst, const void* src, size_t num) {
	assert(dst && src);
	void* ret = dst;

	while (num--) {
		*(char*)dst = *(char*)src;
		((char*)dst)++;
		((char*)src)++;
	}

	return ret;
}

//strcmp

int my_strcmp(const char* src, const char* dst) {
	assert(dst && src);
	while (*src == *dst) {
		//这里说明已经比较完毕，两个字符串相等，返回0
		if (*src == '\0') {
			return 0;
		}
	}

	return (unsigned char)*src - (unsigned char)*dst;
}

char* my_strncat(char* dst, const char* src, size_t num) {
	assert(dst && src);
	char* ret = dst;
	while (*dst) {
		dst++;
	}

	while (num-- && *src) {
		*dst = *src;
		dst++;
		src++;
	}

	*dst = '\0';

	return ret;
}

//char* my_strncpy(char* dst, const char* src, size_t num) {
//	assert(dst && src);
//	char* ret = dst;
//
//	while (num-- && *src) {
//		*dst = *src;
//		dst++;
//		src++;
//	}
//
//	while (num--) {
//		*dst = '\0';
//		dst++;
//	}
//
//	return dst;
//}

//memset
void* my_memset(void* dst, int val, size_t num) {
	assert(dst);
	void* ret = dst;
	while (num--) {
		*(char*)dst = val;
		((char*)dst)++;
	}
	return ret;
}

//memcmp
int my_memcmp(void* dst, void* src, size_t num) {
	assert(dst && src);

	while (num--) {
		if (*(char*)dst != *(char*)src) {
			return (*(char*)dst > *(char*)src) ? 1 : -1;
		}
		((char*)dst)++;
		((char*)src)++;
	}

	return 0;
}

void* my_memmove(void* dst, const void* src, size_t num) {
	assert(dst && src);

	char* ret = dst;
	if (dst > src) {
		//从后往前
		while (num--) {
			//num进入循环，已经减过一次，+num直接指向了最后一个元素
			*((char*)dst + num) = *((char*)src + num);
		}
	}
	else {
		while (num--) {
			*(char*)dst = *(char*)src;
			((char*)dst)++;
			((char*)src)++;
		}
	}

	return ret;
}

//找到str2在str1中的起始位置
char* my_strstr(char* str1, char* str2) {
	char* pos = str1;
	char* c1 = str1;
	char* c2 = str2;

	while (*pos) {
		//每个pos位置比对完，就更新c1和c2位置
		c1 = pos;
		c2 = str2;
		if ((*c1 == *c2) && *c1 && *c2) {
			c1++;
			c2++;
		}

		if (*c2 == '\0') {
			return pos;
		}

		pos++;
	}

	return NULL;
}

//int main() {
//	char s1[20] = "he";
//	char s2[20] = "hello";
//	/*my_strcat(s1, s2);
//	printf("%s ", s1);*/
//	//my_strncpy(s1, s2, 8);
//
//	//memcmp(s1, s2, 2);
//	printf("%d\n", memcmp(s1, s2, 2));
//	return 0;
//}

//void printyhsj(int n) {
//	int arr[30][30] = { 1 };
//
//	for (int i = 0; i < n; ++i) {
//		for (int j = 0; j <= i; ++j) {
//			if (j == 0 || i == j) {
//				arr[i][j] = 1;
//			}
//			else {
//				arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
//			}
//		}
//	}
//
//	for (int i = 0; i < n; ++i) {
//		for (int j = 0; j <= i; ++j) {
//			printf("%d ", arr[i][j]);
//		}
//		printf("\n");
//	}
//}

void printyhsj(int n) {

	int arr[30] = { 1 };
	//先打印第一行
	printf("1\n");

	for (int i = 1; i < n; ++i) {
		for (int j = i; j > 0; --j) {
			arr[j] += arr[j - 1];
		}

		//计算一行打印一行
		for (int j = 0; j <= i; ++j) {
			printf("%d ", arr[j]);
		}
		printf("\n");
	}
}

//日本某地发生了一件谋杀案，警察通过排查确定杀人凶手必为4个嫌疑犯的一个。
//以下为4个嫌疑犯的供词 :
//A说：不是我。
//B说：是C。
//C说：是D。
//D说：C在胡说
//已知3个人说了真话，1个人说的是假话。
//现在请根据这些信息，写一个程序来确定到底谁是凶手。

void GuessK() {
	char k = 0;
	for (k = 'a'; k <= 'd'; ++k) {
		if (((k != 'a') + (k == 'c') + (k == 'd') + (k != 'd')) == 3) {
			printf("killer is %c\n", k);
		}
	}
}

//void GuessK() {
//	char ker = 0;
//	for (ker = "a"; ker <= 'd'; ker++) {
//		//3个人说了真话，1个人说的是假话 也就是四个表达式相加等于3
//		if (((ker != 'a') + (ker == 'c') + (ker == 'd') + (ker != 'd')) == 3) {
//			printf("%c \n", ker);
//		}
//	}
//}

//5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：
//A选手说：B第二，我第三；
//B选手说：我第二，E第四；
//C选手说：我第一，D第二；
//D选手说：C最后，我第三；
//E选手说：我第四，A第一；
//比赛结束后，每位选手都说对了一半，请编程确定比赛的名次。

void GuessN() {
	for (int A = 0; A <= 5; ++A) {
		for (int B = 0; B <= 5; ++B) {
			for (int C = 0; C <= 5; ++C) {
				for (int D = 0; D <= 5; ++D) {
					for (int E = 0; E <= 5; ++E) {
						if ((((B == 2) + (A == 3)) == 1) &&
							(((B == 2) + (E == 4)) == 1) &&
							(((C == 1) + (D == 2)) == 1) &&
							(((C == 5) + (D == 3)) == 1) &&
							(((E == 4) + (A == 1)) == 1) &&
							A * B * C * D * E == 120) {
							printf("A = %d , B = %d , C = %d, D = %d, E = %d \n", A, B, C, D, E);
						}
					}
				}
			}
		}
	}
}


//有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，
// 请编写程序在这样的矩阵中查找某个数字是否存在。
//
//要求：时间复杂度小于O(N);
	// 1 2 3
	// 4 5 6
	// 7 8 9
void yangshijz(int arr[][3], int* px, int* py, int key) {
	int x = 0;
	int y = *py - 1;

	while (x >= 0 && y < *py) {
		if (arr[x][y] > key) {
			y--;
		}
		else if (arr[x][y] < key) {
			x++;
		}
		else {
			*px = x;
			*py = y;
			return;
		}
	}
	*px = -1;
	*py = -1;
}

//实现一个函数，可以左旋字符串中的k个字符。
//例如：
//ABCD左旋一个字符得到BCDA
//ABCD左旋两个字符得到CDAB


//void LeftRound(char* str, int k) {
//	assert(str);
//
//	int len = strlen(str);
//	k %= len;
//	while (k--) {
//		char tmp = *str;
//		for (int i = 0; i < len - 1; ++i) {
//			*(str + i) = *(str + i + 1);
//		}
//		*(str + len - 1) = tmp;
//	}
//}

void reversestr(char* left, char* right) {
	assert(left && right);
	while (left < right) {
		char tmp = *left;
		*left = *right;
		*right = tmp;

		left++;
		right--;

	}
}

void LeftRound(char* str, int k) {
	assert(str);

	size_t len = strlen(str);
	k %= len;
	
	//先反转0-k-1位置
	//再反转k-len-1位置
	//再全部反转
	reversestr(str, str + k - 1);
	reversestr(str + k, str + len - 1);
	reversestr(str, str + len - 1);

}

//写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
//例如：给定s1 = AABCD和s2 = BCDAA，返回1
//给定s1 = abcd和s2 = ACBD，返回0
//AABCD左旋一个字符得到ABCDA
//AABCD左旋两个字符得到BCDAA
//AABCD右旋一个字符得到DAABC

//int findRound(const char* str1, char* str2) {
//	assert(str1 && str2);
//	int len = strlen(str2);
//	int j = 0;
//	
//	while (j--) {
//		char tmp = *str2;
//		for (int i = 0; i < len - 1; ++i) {
//			*(str2 + i) = *(str2 + i + 1);
//		}
//		*(str2 + len - 1) = tmp;
//
//		if (strcmp(str1, str2) == 0) {
//			return 1;
//		}
//	}
//	return 0;
//}

//int findRound(const char* str1, char* str2) {
//	assert(str1 && str2);
//	int len1 = strlen(str1);
//	int len2 = strlen(str2);
//
//	if (len1 != len2) {
//		return 0;
//	}
//
//	char tmp[256] = "";
//
//	strcpy(tmp, str1);
//	strcat(tmp, str1);
//
//	if (strstr(tmp, str2) == NULL) {
//		return 0;
//	}
//	else {
//		return 1;
//	}
//}


//一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
//编写一个函数找出这两个只出现一次的数字。
//例如：
//有数组的元素是：1，2，3，4，5，1，2，3，4，6
//只有5和6只出现1次，要找出5和6

void findTwoNum(int arr[], int n, int* pdog1, int* pdog2) {

	//arr元素全部^ 就能得出 *pdog1 ^ *pdog2 的值

	int ret = 0;

	for (int i = 0; i < n; ++i) {
		ret ^= arr[i];
	}

	//此时找出 ^ 结果的第一位为1 的位置

	int pos = 0;

	for (int i = 0; i < 32; ++i) {
		if (((ret >> i) & 1) == 1) {
			pos = i;
			break;
		}
	}

	//通过pos位置是否为1，把数组中所有数据分成两组

	for (int i = 0; i < n; ++i) {
		if (((arr[i] >> pos) & 1) == 1) {
			(*pdog1) ^= arr[i];
		}
	}

	//此时拥有ret也就是 *pdog1 ^ *pdog2 也有 *pdog1 那么*pdog2 就是ret ^ *pdog1

	(*pdog2) = ret ^ (*pdog1);

}

enum state
{
	FF,
	HF
}state;

int my_atoi(const char* str) {

	int flag = 1;
	//传入空指针
	assert(str);
	//传入空字符串
	if (*str == '\0') {
		return 0;
	}
	//前面是连续空格
	while (isspace(*str)) {
		str++;
	}
	//传入正负号
	if (*str == '-') {
		flag = -1;
		str++;
	}
	else if (*str == '+') {
		str++;
	}
	
	long long ret = 0;

	while (*str) {
		if (isdigit(*str)) {
			//是合法输入
			//计算
			ret = ret * 10 + flag * (*str - '0');

			//输入超出限制的数
			if (ret < INT_MIN || ret > INT_MAX) {
				return 0;
			}
		}
		else {
			//传入非法字符
			return (int)ret;
		}

		str++;
	}
	state = FF;
	return (int)ret;
}



int cmp(void* c1, void* c2) {
	return (*(int*)c1) - (*(int*)c2);
}

void swap(char* s1, char* s2, int type_size) {
	while (type_size--) {
		char tmp = *s1;
		*s1 = *s2;
		*s2 = tmp;
		
		s1++;
		s2++;
	}
}

void my_qsort(int arr[], int num, int type_size, int (*cmp)(void*, void*)) {
	for (int i = 0; i < num; ++i) {
		for (int j = 0; j < i - 1; ++j) {
			if (cmp((arr + (j * type_size)), (arr + ((j + 1) * type_size))) > 0){
				swap((arr + (j * type_size)), (arr + ((j + 1) * type_size)), type_size);
			}
		}
	}
}

//void print_arr(int* arr, int row, int col) {
//	for (int i = 0; i < row * col; ++i) {
//		printf("%d ", arr[i]);
//	}
//}

//void test(char** arr) {
//	printf("%s\n", arr[0]);
//	
//	//printf("%s\n", arr[1]);
//}


#define OFFSETOF(type,member)    (size_t)&(((type*)0)->member)

#define SWAP(n)  ((n) = (((n & 0xaaaaaaaa)>>1) + ((n & 0x55555555)<<1)))

int main() {

	//char* arr[5] = { "hello", "bit" };
	//test(arr);



	//int arr[3][5] = { 1,2,3,4,5,6,7,8,9,10 };
	//print_arr(arr, 3, 5);



	//printyhsj(5);
	//GuessK();
	//GuessN();

	/*int arr[][3] = { 1,2,3,4,5,6,7,8,9 };
	int key = 0;
	scanf_s("%d", &key);
	int x = 3;
	int y = 3;
	yangshijz(arr, &x, &y, key);
	
	if (x == -1 && y == -1) {
		printf("没找到");
	}
	else {
		printf("找到了，下标是arr[%d][%d]", x, y);
	}*/

	/*char str1[] = "abcdef";
	char str2[] = "defabc";
	int ret = findRound(str1, str2);
	if (ret == 1) {
		printf("YES\n");
	}
	else {
		printf("NO\n");
	}*/

	return 0;
}
